package leetcode.code0221;


public class Solution extends Solution221 {

	@Override
	public int maximalSquare(char[][] matrix) {
		int max = 0;
		int n = matrix.length;
		int m = matrix[0].length;
		int[][] square = new int[n][m];// 以nm为右下角是个最大边长为几的正方形
		for (int i = 0; i < m; i++) {
			square[0][i] = matrix[0][i] == '1' ? 1 : 0;
			max = Math.max(max, square[0][i]);
		}
		for (int i = 0; i < n; i++) {
			square[i][0] = matrix[i][0] == '1' ? 1 : 0;
			max = Math.max(max, square[i][0]);
		}
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				if (matrix[i][j] == '1') {
					int len = Math.min(square[i - 1][j - 1], square[i - 1][j]);
					len = Math.min(len, square[i][j - 1]);
					square[i][j] = len == 0 ? 1 : len + 1;
					max = Math.max(max, square[i][j]);
				}
			}
		}
		return max * max;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
		so.debug5();
	}

}
